Data networks that includes multiple clients (such as computers, peripherals, servers, wireless devices, etc.) typically include one or more devices that are responsible to manage communication between multiple clients (otherwise each pair of clients would demand a dedicated connection between the two clients). In packet-based networks, the managing of the communication between the clients is generally carried out by communication switches (widely referred to plainly as switches).
FIG. 1 is a block diagram of prior art switch 100. Switch 100 is adapted to convey information from multiple input ports 112, such as input ports 112(1) through 112(6), to multiple output ports 114, such as output ports 114(1) through 114(6). It is noted that according to some embodiments of prior art switches, at least some ports (not shown) of switch 100 are input/output ports, that are adapted both for reception of data and for transmission of data. For simplicity of explanation output ports are illustrated as being separated from input ports.
Switch 100 is adapted to receive data through input ports 112 in the form of data packets (commonly referred to as packets), wherein each packet includes both a payload, which is the actual data that should be conveyed to one or more destinations, and metadata. Metadata that is joined to the packet ahead of the payload is commonly referred to as header, and typically contains data such as packet length, header length, protocol needed to read the packet, error correction codes, data pertaining to the source of the packet, and data pertaining to the destination of the packet. Metadata that is joined to the packet following the payload is commonly referred to as trailer, and typically includes an end of packet sign. It is noted that different switches are adapted to different communication protocols, and that different communication protocols implement different forms of packets, and therefore different forms of headers and trailers. Notably, most of the switches are adapted to convey packets of different sizes, wherein sizes of packets usually differ from few dozens bits to few dozens kilobytes.
Whenever a packet is received by switch 100, it is processed by processor 120, and, conveniently, by packet processor 122 which is included in processor 120. It is noted that conveniently, packet processor 122 is adapted to process packets in a serial manner. Since packets may arrive at least partially parallel to each other via different ports, switch 100 conveniently includes incoming packets buffer (not shown), that is adapted to store incoming packets until they are processed by packet processor 122.
Packet processor 122 is adapted to separate each incoming packet into the payload, which is saved as a data entity 920 in memory unit 130, and to the metadata, which is further processed by packet processor 122. Packet processor 122 updates the metadata of the packet, so as to include a descriptor that refers to the location of the payload of the packet that is store in memory unit 130. Conveniently, metadata for each packet, and especially a descriptor to the location of the data entity 920 that stores the payload of the packet in memory unit 130, is stored in metadata storage 140, until it could be further processed. According to some embodiments of prior art switches, metadata storage 140 is included in memory unit 130.
Conveniently, memory unit 130 is divided into multiple memory pages 132 which are of identical size. FIG. 1 illustrates two data entities 920 which are stored in memory unit 130 and which stores the payloads of two packets: the size of data entity 920(1) is smaller than the size of the memory pages 132; and therefore, the respective descriptor need to store only the address of a single memory page 132. The size of data entity 920(2) is larger than the size of the memory pages 132, and requires four memory pages 132 to be stored; therefore, the respective descriptor need to store the addresses of four memory pages 132.
It is noted that while data entities 920(2) is illustrated as continuous to data entity 920(1) and as being stored in consecutive memory pages 132, neither in prior art solutions not according to the teaching of the invention must it necessarily be so.
Conveniently, packet processor 122 is adapted to perform a syntax analysis (commonly referred to as parsing) to every incoming packet, to retrieve protocol data of the packet, and to classify the packet according to one or more classifying rules, that pertain to the metadata, and, according to some prior art switches, also to an analysis of the payload.
Following the described actions, packet processor 122 assign each packet to a queue 150 which is assigned to one of the output ports 114, in response to the metadata of each packet, and, according to some prior art switches, according to an analysis of the payload. As illustrated in FIG. 1, multiple queues 150 could be assigned to a single output port 114. For example, the queues denoted as 150(11) through 150(13) are all assigned to port 114(1), the queues denoted as 150(31) and 150(32) are both assigned to port 114(3), and so forth. Conveniently, multiple queues 150 are assigned to a single output port 114 in embodiments of switches in which are different priority levels are assigned to the different packets, wherein each of the queues include packets that have a certain priority level, or which are included in a range of priority levels. Some switches assign multiple queues 150 to a single output port 114 to achieve benefits of assigning of a queue 150 to one or more specific packets providing services (some examples of such benefits are improving the switch communication rate, and improving the performance of one or more services).
According to some embodiments of prior art switches 100, packet manager 124, which is included in processor 120, is adapted to decide whether to admit or to deny each packet to the queue 150 to which it is assigned. Conveniently, packet manager 124 denies packets from being enqueued into a queue 150 when the transmission rate in the respective output port 114 exceeds a predetermined transmission rate threshold that is assigned to said output port 114. Conveniently, drop manager 124 is adapted to delete from memory unit 130 the data entity 920 which stores the payload of the denied packet, and to discard the metadata pertaining to said denied packet.
Packet manager 124 is adapted to create a descriptor 940 to each admitted packet, wherein the descriptor 940 refers to a location of the data entity 920 that includes the payload of the packet. Conveniently, packet manager creates the descriptor 940 in response to the metadata of the respective packet. Conveniently, the descriptors 940 include additional information, such as size of the payload, and so forth; wherein according to different embodiments of prior art switch 100, packet manager 124 add different information to the descriptors 940. Packet manager 124 than enqueues each packet to the queue 150 to which it was assigned.
It is noted that descriptors 940 are represented in FIG. 1 as filled boxes in each queue 150.
Conveniently, each of the queues 150 of prior art switch 100 are ordinary first-in-first-out (FIFO) queues, wherein each packet whose descriptor 940 is included in a queue 150 is transmitted to its destination only after all packets whose descriptors 940 where enqueued to said queue 150 were served.
Packet builder 126, which is conveniently included in processor 120, is responsible to access each of the queues 150 of switch 100 according to an access algorithm (such as, but not limited to, a round robin algorithm. In situations in which different priorities are assigned to different queues 150, the access algorithm is conveniently responsive to the priorities of the different queues. Moreover, different output port priorities could be assigned to the different output ports 114, wherein the access algorithm is further responsive to the output ports priorities). For every queue 150 accessed, packet builder 126 checks if the accessed queue 150 is empty, wherein in such case packet builder 126 proceeds to access queues 150 according to the access algorithm, or else, if the accessed queue 150 stores at least one descriptor 940, packet builder 126 reads the first descriptor 940 in the accessed queue 150, creates a metadata, in response to information included in the descriptor 940 and in the data entity 920 to which the descriptor 940 refers, creates a new packet from said data entity 920 and the created metadata, and provide the new packet to the output port 114 specified in the descriptor 940, to be transmitted to the destination of the packet.
The computing power demanded by a switch is provided by a processor, which is commonly implemented on a field programmable gate array (FPGA) chip. FPGA chips are reconfigurable, what facilitates the planning of the processor, and the processor itself more flexible in many ways. Communication needs of networks, however, are growing rapidly over the years, as typical networks serves ever growing number of clients, and as the communication rate of each client is increasing on the double. On top of superior computing abilities, contemporary switches are demanding increasing amounts of memory storage. Since the memory available on the field programmable gate array chip is limited and costly, it is customary practice to use an external memory units, and especially double-data-rate synchronous dynamic random access (DDR SDRAM) memory units, to support the memory requirements of chips.
External memory units, and especially DDR SDRAM memory units, however, suffer from considerable latency times, i.e. there is a considerable delay from the moment data is sent to the DDR SDRAM until the data is actually written and acknowledged, and the is a considerable delay from the moment a request for data is sent to the DDR SDRAM until the data is provided by the DDR SDRAM.
Therefore, there is a growing need for switches that can facilitate the memory capacity potential of external memory units, and especially of DDR SDRAM, while countering the potential shortcoming of latency times.
Conventionally, many prior switches encounter difficulties in multicasting packets, wherein multicasting packets loads the switch, and may postpone a transmission of higher priority transmissions.
There is a growing need for reliable and simple means of transmitting packets by switches, and especially means of multicasting packets efficiently.